package offer;

import java.util.*;

public class offerII_0082 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result=new LinkedList<>();
        Set<Integer> set=new HashSet<>();
        List<Integer> path=new LinkedList<>();
        Arrays.sort(candidates);
        search(result,path,target,0,0,candidates,set);
        return result;
    }
    public void search(List<List<Integer>> result,List<Integer> path,int target,int sum,int index,int[] candidates,Set<Integer> set){
        if(sum==target){
            result.add(new ArrayList<>(path));
            return;
        }
        if(sum>target||index== candidates.length) return;
        for(int i=index;i< candidates.length;++i){
            if(!set.contains(candidates[i])){
                set.add(candidates[i]);
                HashSet<Integer> set1=new HashSet<>();
                path.add(candidates[i]);
                search(result, path, target, sum+candidates[i], i+1, candidates, set1);
                path.remove(path.size()-1);

            }
        }
    }
}
